package algorithm.divide.basic;

import algorithm.graph.basic.Graph;

/**
 * 项目名称: god
 * 包 名 称: algorithm.divide.basic
 * 类 名 称: SubArray
 * 类 描 述: TODO
 * 创建时间: 2020/7/14 10:43 上午
 * 创 建 人: Justice
 * 给定一个长度为n的整数序列，求它的最大连续子序列和
 * 例如 -2、1、-3、4、-1、2、1、-5、4
 * 4、-1、2、1
 */
public class SubArray {
    // 暴力解法
    public static int maxSubarray1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = 0; end < nums.length; end++) {
                // sum是[begin, end]的和
                int sum = 0;
                for (int i = begin; i <= end; i++) {
                    sum += nums[i];
                }
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    // n^2
    public static int maxSubarray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            int sum = 0;
            for (int end = begin; end < nums.length; end++) {
                // sum是[begin, end]的和
                sum += nums[end];
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    // 分治法
    public static int maxSubarray3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return maxSubArray(nums, 0, nums.length);
    }

    public static int maxSubArray(int[] nums, int begin, int end) {
        if (end - begin < 2) return nums[begin];
        int middle = (begin + end) >> 1;
        int leftMax = nums[middle - 1];
        int leftSum = leftMax;
        for (int i = middle - 2; i >= begin; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }

        int rightMax = nums[middle];
        int rightSum = rightMax;
        for (int i = middle + 1; i < end; i++) {
            rightSum += nums[i];
            rightMax = Math.max(rightMax, rightSum);
        }

        // 最大子序列，三种可能
        // 全部左边 全部右边 左边一部分 右边一部分
        return Math.max(
                leftMax + rightMax,
                Math.max(
                        maxSubArray(nums, begin, middle),
                        maxSubArray(nums, middle, end))
        );
    }
}
